We consider the problem of scheduling communication on optical WDM(wavelength division multiplexing) networks using the light-trails technology.We seek to design scheduling algorithms such that the given transmissionrequests can be scheduled using minimum number of wavelengths (opticalchannels). We provide algorithms and close lower bounds for two versions of theproblem on an $n$ processor linear array/ring network. In the {\em stationary}version, the pattern of transmissions (given) is assumed to not change overtime. For this, a simple lower bound is $c$, the congestion or the maximumtotal traffic required to pass through any link. We give an algorithm thatschedules the transmissions using $O(c+\log{n})$ wavelengths. We also show apattern for which $\Omega(c+\log{n}/\log\log{n})$ wavelengths are needed. Inthe {\em on-line} version, the transmissions arrive and depart dynamically, andmust be scheduled without upsetting the previously scheduled transmissions. Forthis case we give an on-line algorithm which has competitive ratio$\Theta(\log{n})$. We show that this is optimal in the sense that every on-linealgorithm must have competitive ratio $\Omega(\log{n})$. We also give analgorithm that appears to do well in simulation (for the classes of traffic weconsider), but which has competitive ratio between $\Omega(\log^2n/\log\log{n})$ and $O(\log^2n)$. We present detailed simulations of both ouralgorithms.
展开▼
